Conjunto finito no vacio, sin elementos que se obtengan por yuxtaposicion (poner dos letras consecutivas).
Se simboliza con la letra V o con ∑
Palabra: secuencia finita de letras.
Palabra nula: esta formada por 0 letras se simboliza con λ.
Longitud: cantidad de letras que la forman.
Clausura de Kleene de un Alfabeto
V∗=V0∪V1∪V2∪⋯VnVi: conjunto de palabras de longitud i formadas con las letras del alfabeto V
Entonces V∗ sera el conjunto de todas las palabras, de cualquier longitud, que se puede escribir con letras del alfabeto.
∣Vn∣=n∣V∣
long(w1⋅w2)=long(w1)+long(w2)
w1⋅(w2⋅w3)=(w1⋅w2)⋅w3
Inversion o trasposicion: es la palabra que se obtiene al escribir dicha palabra de "atras hacia adelante" se simboliza wR
wRR=w
(w1⋅w2)R=w2R⋅w1R
λR=λ
long(wR)=long(w)
Sea w una palabra ∈V∗,w es palindromo ⟺w=wR
Sea w∈V∗ se define:
⎩⎨⎧w0=λw1=wwn=w⋅wn−1con n∈N0
long(wn)=n⋅long(w)
Lenguaje
Sea L un conjunto y V un alfabeto. L es un lenguaje ⟺L⊆V∗
Los lenguajes pueden ser finitos o infinitos
Como L⊆V∗ entonces L∈P(V∗)
L al ser un conjunto se le pueden aplicar operaciones de conjuntos.
L puede no tener ningun elemento.
L={λ}=Λ se llama lenguaje nulo.
L=∅ se llama lenguaje vacio (no tiene palabras).
Concatencaion de Lenguajes
L=L1⋅L2={xy/x∈L1∧y∈L2}
∣L1⋅L2∣≤∣L1∣⋅∣L2∣
(P(V∗);∙) semigrupo con neutro L=Λ
L1⋅L2=L2⋅L1
L=∅ es elemento absorbente de la concatenacion.
Si L1⊂L2 y L3⊂L4 entonces L1⋅L3⊂L2⋅L4
Lenguaje inverso reflejo o traspuesto:
LR={wR/w∈L}, son todas las palabras del lenguaje reflejadas.
Potencia de un Lenguaje
⎩⎨⎧L0={λ}L1=LLn=L⋅Ln−1con n∈N0
Clausura de Kleene de un Lenguaje
L∗=⋃n=0∞Ln=L0∪L1∪L2∪⋯∪Ln∪⋯
Λ∗=Λ
∅∗=Λ
∀L:λ∈L∗
Clausura Positiva de un Lenguaje
L+=⋃n=1∞Ln=L1∪L2∪⋯∪Ln∪⋯
Λ+=λ
∅+=∅
Complemento de un Lenguaje
L=V∗−L
Gramatica
G=(Vn;Vt;P;S)Vn: Vocabulario o alfabeto de no terminales.Vt: Vocabulario o alfabeto de Terminales. Letras con las que se forman las palabras.P: Producciones.S: Simbolo o variable inicial.
Vn y Vt son conjuntos finitos
Vn∩Vt=∅
P es finito y P⊂(V+−Vt∗)×V∗ sinedo V=Vn∪Vt
S pertenece a Vn
P es finito y P⊂(V+−Vt∗)×V∗ sinedo V=Vn∪Vt
V∗ Sin restriccion
V+−Vt∗ Sin restriccion
las no terminales son las variables que generan las palabras
terminales son las letras con las que se forman las palabras
El lenguaje generado por la gramatica G se llama L(G)
Tipos de Gramaticas (Jerarquia de Chomsky)
Tipo
Nombre
Producciones
0
Irrestricta
Cualquier forma
1
Sensible al Contexto
aXb→aYb donde a,b,Y∈V∗X∈Vn
2
Independiente del Contexto
X→Y donde X∈Vn
3
Regular
X→Y donde X∈VnY puede ser Vt,t o λ (derecha) Y puede ser tV,t o λ (izquierda)
Un lenguaje se dice de tipo K sii existe una gramatica detipo k que la genere.
Casi todos los lenguajes de programacion son de tipo 2
L3⊆L2⊆L1⊆L0
Un lenguaje puede estar generado por distintas gramaticas de distinto tipo para un mismo lenguaje, pero el tipo del lenguaje sera el de la gramatica de mayor tipo.
Cada gramatica genera un unico lenguaje
Cada lenguaje puede ser generado por muhas gramaticas.
Expresiones Regulares
Una ER es una secuencia de elementos que verifica:+
λ es ER
a∈V entocnes a es ER
Si X,Y son ER entonces X⋅Y es ER
Si X,Y son ER entonces X+Y es ER
Si X es ER entonces X∗ es ER
Automatas Finitos
Maquinas de estados finitos
Lenguaje Tipo
Maquina que lo Reconoce
0
Mauina de Turing
1
Automata linealmente Acotado
2
Automata de Pila (Push Down)
3
Automata Finito
Automata Finito
A=(Q,V,λ,q0,F)Q: Conjunto finito de estados
V: vocabulario o alfabeto de enrtada
λ:Q×V→Q. Funcion de transision
q0: Estado Inicial
F: Conjunto de estados finales F=∅ y F⊂Q
x
y
q0
q0,q1
q1
q1
q2
q2
q1
la primer columna son los estados posibles del automata
la primer fila son las letras del alfabeto
lo que hay en cada celda es a que estado se dirige si se elige una letra.
AFD: no tiene transisciones por λ, cumple con ley de unicidad. Osea, no usa el caracter λ para alguna de las aristas, y no presenta dos posibles caminos para el mismo caracter.